package com.lee.algorithm.tree;

import com.lee.algorithm.tree.struct.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/***
 * @description: 搜索二叉树
 *      节点的左子树都比它小，同时它的右子树都比他大
 * @author : 青石路
 * @date: 2021/12/5 20:43
 */
public class SearchBinaryTree {

    public static int preValue = Integer.MIN_VALUE;         // 当前处理节点的 前一个被处理的节点的值

    public static boolean isSBT(TreeNode<Integer> head) {
        if (head == null) {
            return true;
        }

        // 检查左子树是否是搜索二叉树
        boolean isLeftBST = isSBT(head.left);
        if (!isLeftBST) {
            return false;
        }

        // 当前节点判断
        if (head.value <= preValue) {
            return false;
        } else {
            preValue = head.value;
        }

        // 检查右子树是否是搜索二叉树
        return isSBT(head.right);
    }

    public static boolean isSBT2(TreeNode<Integer> head) {
        List<Integer> list = new ArrayList<>();
        process(head, list);
        int preValue = Integer.MIN_VALUE;
        for (int cur : list) {
            if (cur <= preValue) {
                return false;
            }
            preValue = cur;
        }
        return true;
    }
    private static void process(TreeNode<Integer> head, List<Integer> list) {
        if (head == null) {
            return;
        }
        process(head.left, list);
        list.add(head.value);
        process(head.right, list);
    }


    /**
     * 非递归
     * @param head
     * @return
     */
    public static boolean isSBTUnRecur(TreeNode<Integer> head) {
        if (head != null) {
            int preValue = Integer.MIN_VALUE;
            Stack<TreeNode<Integer>> stack = new Stack<>();
            TreeNode<Integer> cur = head;
            while (!stack.isEmpty() || cur != null) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    if (cur.value <= preValue) {
                        return false;
                    } else {
                        preValue = cur.value;
                    }
                    cur = cur.right;
                }
            }
        }
        return true;
    }

    /**
     * 树形递归
     *      对于任意一个节点 X，它的左子树是二叉搜索树，它的右子树也是二叉搜索树
     *      并且左子树的最大值小于 X，右子树的最小值大于 X
     *
     *      向左子树要的信息：1.是否是搜索二叉树，2.最大值
     *      向右子树要的信息：1.是否是搜索二叉树，2.最小值
     *      取左右子树的信息全集作为信息结构体：ReturnData
     * @return
     */
    public static boolean isSBT3(TreeNode<Integer> root) {
        return judgeSBT(root).isSBT;
    }

    /**
     * 信息结构体
     */
    static class ReturnData {
        boolean isSBT;
        int max;
        int min;

        ReturnData (boolean isSBT, int max, int min) {
            this.isSBT = isSBT;
            this.max = max;
            this.min = min;
        }
    }

    public static ReturnData judgeSBT(TreeNode<Integer> node) {
        if (node == null) {     // base case
            // 不太好处理，isSBT 可以设置成 true，但 max、min 设置成什么都不合适
            // 所以直接返回 null，让上游调用者自己去处理
            return null;
        }

        ReturnData leftData = judgeSBT(node.left);
        ReturnData rightData = judgeSBT(node.right);

        int max = node.value;
        int min = node.value;
        if (leftData != null) {
            max = Math.max(leftData.max, max);
            min = Math.min(leftData.min, min);
        }
        if (rightData != null) {
            max = Math.max(rightData.max, max);
            min = Math.min(rightData.min, min);
        }

        boolean isSBT = true;
        if (leftData != null
                && (!leftData.isSBT || leftData.max >= node.value)) {
            isSBT = false;
        }
        if (rightData != null
                && (!rightData.isSBT || leftData.min <= node.value)) {
            isSBT = false;
        }
        return new ReturnData(isSBT, max, min);
    }
}
